/*
  Knapsack problem implemented by dynamic programing
*/

#include<stdio.h>
#define C 10	//capacity of the knapsack
#define NUM 5	//number of the products

const int weight[] = {0, 2, 2, 6, 5, 4};	//weight of the products
const int value[] = {0, 6, 3, 5, 4, 6};	//value of the products
const int len =  sizeof(weight)/sizeof(weight[0]) - 1;	//length of the weight and value
int option[NUM];	//the option of products

void dyPro(int optiArray[][C+1], const int weight[], const int value[], const int num)
{
	int i, j;

/*******************initialize the first row and column of optiArray*****************/

	for(i = 0; i <= len; i++)
		optiArray[i][1] = 0;
	for(j = 0; j <= C; j++)
		optiArray[1][j] = 0;

/*******************load the nth product*********************************************/

	for(j = 1; j <= C; j++)
	{
		if(j < weight[len])
			optiArray[len][j] = 0;
		else
			optiArray[len][j] = value[len];
	}

/*******************load the top n-1 products****************************************/
	for(i = len-1; i>=1; i--)
	{
		for(j =1; j <= C; j++ )
		{
			if(j < weight[i])
				optiArray[i][j] = optiArray[i+1][j];
			else
				optiArray[i][j] = optiArray[i+1][j] > optiArray[i+1][j-weight[i]]+value[i] ? optiArray[i+1][j] : optiArray[i+1][j-weight[i]]+value[i];
		}
	}

}

/*******************optimized option of the products*********************************/
void optionFun(int optiArray[][C+1], const int num)
{
        int i, j;
        for(i = 1, j = C; i <= num-1; i++)
        {
                if(optiArray[i][j] == optiArray[i+1][j])
			option[i-1] = 0;
		else
		{
			option[i-1] = 1;
			j = j - weight[i];
		}		
        }
	i -= 1;
	option[i] = optiArray[num][j] ? 1:0;
}

int main()
{
	int optiArray[NUM+1][C+1] = {0};
	int i,j;

	dyPro(optiArray, weight, value, len);
	for(i = 0; i <= len; i++)
	{
		for(j = 0; j <= C; j++)
			printf("%3d ", optiArray[i][j]);
		printf("\n");
	}
	optionFun(optiArray, len);
	
	printf("\nThe option of the products are: ");
	for(i = 0; i < NUM; i++)
		printf("%d ", option[i]);
	printf("\n");
	return 1;
}
